/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._572;

/**
 *
 * 给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
 *
 * 示例 1:
 * 给定的树 s:
 *
 *      3
 *     / \
 *    4   5
 *   / \
 *  1   2
 * 给定的树 t：
 *
 *    4
 *   / \
 *  1   2
 * 返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
 *
 * 示例 2:
 * 给定的树 s：
 *
 *      3
 *     / \
 *    4   5
 *   / \
 *  1   2
 *     /
 *    0
 * 给定的树 t：
 *
 *    4
 *   / \
 *  1   2
 * 返回 false。
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._572
 * @ClassName: Subtree
 * @Author: linyaonan
 * @Date: 2020/1/3 10:53
 */
public class Subtree {

    public boolean isSubtree(TreeNode s, TreeNode t) {
        return isChildTree(s, t);
    }

    /**
     * 遍历每个节点，然后比较
     * @param node
     * @param t
     * @return
     */
    private boolean isChildTree(TreeNode node, TreeNode t) {
        if (nodeEqual(node, t)) {
            return true;
        } else {
            if (node.left != null) {
                if (isChildTree(node.left, t)) {
                    return true;
                }
            }
            if (node.right != null) {
                return isChildTree(node.right, t);
            }
        }

        return false;
    }

    /**
     * 节点比较的函数
     * @param a
     * @param b
     * @return
     */
    private boolean nodeEqual(TreeNode a, TreeNode b) {
        if (a != null && b != null) {
            if (a.val == b.val) {
                if (!nodeEqual(a.left, b.left)) {
                    return false;
                }
                return nodeEqual(a.right, b.right);
            } else {
                return false;
            }
        } else {
            return a == null && b == null;
        }
    }
}
